﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//剑指 Offer II 064. 神奇的字典❤️
struct Trix
{
	vector<Trix*> _children;
	bool _isEnd;
	Trix()
		:_children(26, nullptr)
		, _isEnd(false)
	{}
	void InsertStr(string word)
	{
		Trix* node = this;

		for (auto ch : word)
		{
			ch -= 'a';
			if (node->_children[ch] == nullptr)
			{
				node->_children[ch] = new Trix();
			}
			node = node->_children[ch];
		}
		node->_isEnd = true;
	}
};
class MagicDictionary {
public:
	bool dfs(Trix* root, string& searchWord, int i, int edit)
	{
		if (root == nullptr)
		{
			return false;
		}
		//满足这三个条件才匹配成功
		if (root->_isEnd && i == searchWord.size() && edit == 1)
		{
			return true;
		}

		if (i < searchWord.size() && edit <= 1)
		{
			bool found = false;
			//穷举
			for (int j = 0; j < 26 && !found; j++)
			{
				//用三木运算符判断是否需要替换
				int next = (j == searchWord[i] - 'a') ? edit : edit + 1;
				found = dfs(root->_children[j], searchWord, i + 1, next);
			}
			return found;
		}
		return false;
	}
	/** Initialize your data structure here. */
	MagicDictionary()
	{
		_root = new Trix();
	}
	void buildDict(vector<string> dictionary)
	{
		for (auto& word : dictionary)
		{
			_root->InsertStr(word);
		}
	}

	bool search(string searchWord)
	{
		return dfs(_root, searchWord, 0, 0);
	}
private:
	Trix* _root;
};

//剑指 Offer II 065. 最短的单词编码❤️
struct Trix
{
	vector<Trix*> _children;
	int _count = 0;//计数
	Trix()
		:_children(26, nullptr)
	{}
	Trix* Get(char c)
	{
		if (_children[c - 'a'] == nullptr)
		{
			_children[c - 'a'] = new Trix();
			_count++;
		}
		return _children[c - 'a'];
	}
};
class Solution {
public:
	int minimumLengthEncoding(vector<string>& words) {
		Trix* tr = new Trix();
		unordered_map<Trix*, int>hash;
		int n = words.size();
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			string word = words[i];
			Trix* cur = tr;
			//从后缀插入
			for (int j = word.size() - 1; j >= 0; j--)
			{
				cur = cur->Get(word[j]);
			}
			hash[cur] = i;
		}
		unordered_map<Trix*, int>::iterator it = hash.begin();
		while (it != hash.end())
		{
			if (it->first->_count == 0)
			{
				cnt += words[it->second].size() + 1;
			}
			++it;
		}

		return cnt;
	}
};